#include <stdio.h>
void Swap(int *p1,int*p2)
{
	int tmp=*p1;
	*p1=*p2;
	*p2=tmp;
	
}
void Print(int*a,int n)
{
	for(int i=0;i<n;i++)
		{
			printf("%d ",a[i]);
		}
	printf("\n");
}
void AdJustDown(int* a, int n, int root)
{
	int father=root;
	int child= father*2+1;
	while(child<n)
		{
			if(a[child]<a[child+1])
				{
					child=child+1;
				}
			if(a[father]<a[child])
				{
					Swap(&a[father], &a[child]);
					father=child;
					child=father*2+1;
				}
			else
				{
					break;
				}
		}
	
}
void HeapSort(int*a,int n)
{
	int father=(n-1)/2-1;
	
	int i;
	for(i =father;i>=0;i--)
		{
			AdJustDown(a,n,i);
		}
	for( i=n-1;i>0;i--)
		{
			AdJustDown(a,i,0);
			Swap(&a[0], &a[i]);
		}
}
int main(int argc, char *argv[]) 
{
	int arr[]={54,38,96,23,15,72,60,45,83};
	Print(arr,sizeof(arr)/sizeof(arr[0]));
	HeapSort(arr, sizeof(arr)/sizeof(arr[0]));
	Print(arr,sizeof(arr)/sizeof(arr[0]));
	
}